USACO 2024 December Contest, Bronze

[USACO24DEC] Roundabount Rounding B

题目描述

奶牛 Bessie 回到学校了！她开始做她的数学作业，在作业中她被要求将正整数四舍五入到 $10$ 的幂。

要将一个正整数 $a$ 四舍五入到最接近的 ${10}^b$，其中 $b$ 为正整数，Bessie 首先找到从右往左数第 $b$ 个数位。令 $x$ 为这个数位。

如果 $x\ge 5$，Bessie 将 $a$ 增加 ${10}^b$。

然后，Bessie 将从右侧开始直至第 $b$ 个数位的所有数位均设置为 $0$。

例如，如果 Bessie 想要将 $456$ 四舍五入到最接近的 ${10}^2$（百位），Bessie 会首先找到从右往左数第 $2$ 个数位 $5$。这意味着 $x=5$。然后由于 $x\ge 5$，Bessie 将 $a$ 增加 $100$。最后，Bessie 将 $a$ 中从右侧开始直至第 $2$ 个数位的所有数位设置为 $0$，结果为 $500$。

但是，如果 Bessie 将 $446$ 四舍五入到最接近的 ${10}^2$，她将得到 $400$。

在看了 Bessie 的作业后，Elsie 认为她已经发明了一种新的舍入方式：链式舍入。要链式舍入到最接近的 ${10}^b$，Elsie 将首先舍入到最接近的 ${10}^1$，然后舍入到最接近的 ${10}^2$ ，以此类推，直至舍入到最接近的 ${10}^b$。

Bessie 认为 Elsie 是错误的，但她太忙于数学作业，无法确认她的怀疑。她请你计算出存在多少个不小于 $2$ 且不超过 $N$ 的整数 $x$（$1\le N\le {10}^9$），使得将 $x$ 四舍五入到最接近的 ${10}^P$ 与链式舍入到最接近的 ${10}^P$ 的结果不同，其中 $P$ 是满足 ${10}^P\ge x$ 的最小整数。

输入格式

你需要回答多个测试用例。

输入的第一行包含一个整数 $T$（$1\le T\le {10}^5$），为测试用例的数量。以下是 $T$ 个测试用例。

每个测试用例的输入仅有一行，包含一个整数 $N$。输入保证同一测试点中的所有 $N$ 各不相同。

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示存在多少个不小于 $2$ 且不超过 $N$ 的整数在使用两种舍入方法时会得到不同的结果。

输入输出样例 #1

输入 #1

4
1
100
4567
3366

输出 #1

0
5
183
60

说明/提示

样例解释

考虑样例中的第二个测试用例。$48$ 应当被计算在内，因为 $48$ 链式舍入到最接近的 ${10}^2$ 是 $100$（$48\to 50\to 100$），但 $48$ 四舍五入到最接近的 ${10}^2$ 是 $0$。

在第三个测试用例中，$48$ 和 $480$ 是两个被计算在内的整数。$48$ 链式舍入到 $100$ 而不是 $0$，$480$ 链式舍入到 $1000$ 而不是 $0$。但是，$67$ 不被计算在内，因为它链式舍入到 $100$，与 $67$ 四舍五入到最接近的 ${10}^2$ 相同。

测试点性质

• 测试点 1：样例。
• 测试点 2-4：$N\le {10}^3$。
• 测试点 5-7：$N\le {10}^6$。
• 测试点 8-13：没有额外限制。

代码案例

#include"iostream"
#include"algorithm"
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
int n,t,tot;

int round(int x, int target) { // x 四舍五入到 target 位
    if(x % target >= target / 2) return x + target - x % target;
    return x - x % target;
}

int chain_round(int x, int target) { // 链式舍入
    for(int i = 10; i <= target; i *= 10) x = round(x, i);
    return x;
}
void init() {
	int i,j=0,target;
    for(i = 2; i <= 1e6; ++i) {
        target = 1;
        while(target < i) target *= 10;//10^p
        if(round(i, target) != chain_round(i, target)){
        	a[i]=a[i-1]+1;
		}else{
			a[i]=a[i-1];
		}
    }
}

//void print(){
//	int i,j=0,target;
//    for(i = 2; i <= 1e6; ++i) {
//        target = 1;
//        while(target < i) target *= 10;
//        if(round(i, target) != chain_round(i, target))a[t++]=i;
//    }
//    for(i=0;i<100;i++){
//    	cout<<a[i]<<endl;
//	}
//}

int main() {
    init();
//	print();
    cin>>t;
    while(t--) {
        cin>>n;
        cout<<a[n]<<endl;
    }
    
    return 0;
}

const int a[] = {0, 45, 445, 4445, 44445, 444445, 4444445, 44444445, 444444445};
const int b[] = {0, 49, 499, 4999, 49999, 499999, 4999999, 49999999, 499999999};
int n, t;

int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        int ans = 0;
        for(int i = 1; i <= 8; ++i) {
            if(n >= b[i]) ans += b[i] - a[i] + 1;
            else if(n >= a[i]) ans += n - a[i] + 1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

经验

- 0.仔细看题，把案例全部看懂。
- 1.铜牌的题从循环模拟(暴力枚举)的角度去做。(一维数组、二维数组)
- 2.计算时间复杂度去判断我们的模拟过程是否合理。
- 3.如果不合理，需要考虑空间换时间，利用好数组前缀和/前缀积/占位计数等。
- 4.如果时间复杂度连最基本的一层for都满足不了，那么结果数据一定有规律或者利用公式去解决O(1)，可以打表观察。
- 5.考虑数据类型是否会溢出。

[USACO24DEC] Farmer John's Cheese Block B

题目描述

Farmer John 有一块立方体形状的奶酪，它位于三维坐标空间中，从 $(0,0,0)$ 延伸至 $(N,N,N)$（$2\le N\le 1000$）。Farmer John 将对他的奶酪块执行一系列 $Q$（$1\le Q\le 2\cdot {10}^5$）次更新操作。

对于每次更新操作，FJ 将从整数坐标 $(x,y,z)$ 到 $(x+1,y+1,z+1)$ 处切割出一个 $1\times 1\times 1$ 的奶酪块，其中 $0\le x,y,z<N$。输入保证在 FJ 切割的位置上存在一个 $1\times 1\times 1$ 的奶酪块。由于 FJ 正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。

在每次更新后，输出 FJ 可以将一个 $1\times 1\times N$ 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 $[0,N]$。FJ 可以随意旋转砖块。

输入格式

输入的第一行包含 $N$ 和 $Q$。

以下 $Q$ 行包含 $x$，$y$ 和 $z$，为要切割的位置的坐标。

输出格式

在每次更新操作后，输出一个整数，为所求的方案数。

输入输出样例 #1

输入 #1

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

输出 #1

0
0
1
2
5

说明/提示

样例解释

在前三次更新操作后，$[0,1]\times [0,2]\times [0,1]$ 范围的 $1\times 2\times 1$ 砖块与剩余的奶酪不重叠，因此它贡献了答案。

测试点性质

• 测试点 1：样例。
• 测试点 2-4：$N\le 10$ 且 $Q\le 1000$。
• 测试点 5-7：$N\le 100$ 且 $Q\le 1000$。
• 测试点 8-16：没有额外限制。

代码案例

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1001;
int x[MAXN][MAXN], y[MAXN][MAXN], z[MAXN][MAXN], n, q, a, b, c, ans = 0;

int main() {
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		cin >> a >> b >> c;
        // 判断的代码
		if (++x[a][b] == n) ans++;
		if (++y[a][c] == n) ans++;
		if (++z[b][c] == n) ans++;
		cout << ans << endl;
	}
	return 0;
}

[USACO24DEC] It's Mooin' Time B

题目描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个长度为 $N$（$3\le N\le 20000$）的小写字母字符串。一种哞叫一般地定义为子串 $c_i{c}_j{c}_j$，其中某字符 $c_i$ 之后紧跟着 $2$ 个某字符 $c_j$，且 $c_i\ne c_j$。根据 Farmer John 的说法，Bessie 哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 $F$（$1\le F\le N$）次，那可能就是 Bessie 发出的。

然而，Farmer John 的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。将可能的误差考虑在内，输出所有可能是 Bessie 发出的哞叫，按字典序顺序排序。

输入格式

输入的第一行包含 $N$ 和 $F$，表示字符串的长度以及 Bessie 的哞叫的频次下限。

第二行包含一个长度为 $N$ 的小写字母字符串，表示竞赛。

输出格式

输出可能是 Bessie 发出的哞叫的数量，以下是按字典序排序的哞叫列表。每行输出一种哞叫。

输入输出样例 #1

输入 #1

10 2
zzmoozzmoo

输出 #1

1
moo

输入输出样例 #2

输入 #2

17 2
momoobaaaaaqqqcqq

输出 #2

3
aqq
baa
cqq

输入输出样例 #3

输入 #3

3 1
ooo

输出 #3

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

说明/提示

样例 #1 解释

在这个样例中，任何字符变化都不会影响答案。唯一 Bessie 可能发出的哞叫是 $\mathtt{m}\mathtt{o}\mathtt{o}$。

样例 #2 解释

在这个样例中，位置 $8$（从零开始索引）的 $\mathtt{a}$ 可能是由 $\mathtt{b}$ 损坏导致的，这使得 $\mathtt{b}\mathtt{a}\mathtt{a}$ 成为一种 Bessie 发出两次的可能的哞叫。此外，位置 $11$ 的 $\mathtt{q}$ 可能是由 $\mathtt{c}$ 损坏导致的，这使得 $\mathtt{c}\mathtt{q}\mathtt{q}$ 成为一种 Bessie 可能的哞叫。$\mathtt{a}\mathtt{q}\mathtt{q}$ 可以通过将 $\mathtt{c}$ 换成 $\mathtt{a}$ 来达到。

测试点性质

• 测试点 1-3：样例。
• 测试点 4-8：$N\le 100$。
• 测试点 9-13：没有额外限制。

代码案例

思路

注意到 n≤20000，考虑直接暴力。每次枚举合法的（*c*i*=*c*j*） *ci* 和 c**j，然后对「竞赛」字符串进行判断。

我们遍历查找每一个「哞哞叫」字符串在「竞赛」字符串中出现了多少次：

• 如果出现次数大于等于 F，那么这个「哞哞叫」字符串就是正确的。
• 如果出现次数刚好等于 F−1，那么考虑「竞赛」字符串损坏了。我们再遍历一次「竞赛」字符串，如果修改一个之前没有用过的字符可以变成这个「哞哞叫」字符串，那么这个「哞哞叫」字符串就是正确的。

该算法时间复杂度为 O(m2N)，其中 m=26。

#include"iostream"
#include"algorithm"
using namespace std;
int n,f;
string s;
string ss[20005];
bool check(string s2){
	int i,j,k=0;
	int b[20005]={0};
	for(i=0;i<s.size()-2;i++){
		if(s[i]==s2[0]&&s[i+1]==s2[1]&&s[i+2]==s2[2]){
			k++;
			b[i]=b[i+1]=b[i+2]=1;//当前字符已被使用 
		}
	}
	if(k>=f){
		return true;
	}else if(k+1==f){
		for(i=0;i<s.size()-2;i++){
			if(s[i]==s2[0]&&(s[i+1]==s2[1]&&b[i+2]==0 || s[i+2]==s2[2]&&b[i+1]==0)) return true;
			if(b[i]==0 && s[i+1]==s2[1] && s[i+2]==s2[1]) return true;
		}
	}
	return false;
}
int main(){
	char i,j;
	int ans=0,k=0;
	cin>>n>>f>>s;
	for(i='a';i<='z';i++){
		string s2="";
		s2+=i;
		for(j='a';j<='z';j++){
			if(i==j){
				continue;
			}
			s2+=j;
			s2+=j;
//			cout<<s2<<endl;
			if(check(s2)){
				ans++;
				ss[k++]=s2;
			}
			s2="";
			s2+=i;
		}
	}
	cout<<ans<<endl;
	for(i=0;i<k;i++){
		cout<<ss[i]<<endl;
	}
	return 0;
}